#include "leecode.h"

struct Position {
  int i;
  int j;
};

class Solution {
public:
  int maxMoves(std::vector<std::vector<int>>& grid) {
    m_row = grid.size();
    m_grid = &grid;
    m_column = grid[0].size();
    int maxMove = 0;
    for (int i = 0; i < m_column; i++) {
      std::stack<Position> paths;
      Position position = { 0, i};
      paths.push(position);
      LOGGER_DEBUG("pop:[ %d, %d]", paths.top().i, paths.top().j);
      moveForward(paths);
      if(m_maxValue == m_column)
        break;
    }

    return m_maxValue - 1;
  }


  bool forwardInternal(Position& newPos, std::stack<Position>& newPath, int oldPath) {
    static int icount = 0;
    icount++;

    if (newPath.size() == m_column) {
      m_maxValue = m_column;
      return false;
    }
    
    if ((*m_grid)[newPos.i][newPos.j] > (*m_grid)[newPath.top().i][newPath.top().j]) {
      newPath.push(newPos);
      LOGGER_DEBUG("push:[ %d, %d]", newPath.top().i, newPath.top().j);
      moveForward(newPath);

      if (m_maxValue < newPath.size())
        m_maxValue = newPath.size();

      LOGGER_DEBUG("%d times, maxValue: %d]", icount, m_maxValue);

      for (int i = 0; i < newPath.size() - oldPath; i++) {
        LOGGER_DEBUG("pop:[ %d, %d]", newPath.top().i, newPath.top().j);
        newPath.pop();
      }
      return true;
    }
    return false;
  }

  bool moveForward(std::stack<Position>& paths) {
    Position position = paths.top();
    bool isForward = false;

    int oldPath = paths.size();

    if (oldPath == m_column)
      return oldPath;

    if (position.j < m_column - 1) {
      Position newPos = { position.i , position.j + 1 };
      isForward = forwardInternal(newPos, paths, oldPath) || isForward;

      if (position.i > 0) {
        Position newPos = { position.i - 1 , position.j + 1 };
        isForward = forwardInternal(newPos, paths, oldPath) || isForward;
      }


      if (position.i < m_row - 1) {
        Position newPos = { position.i + 1 , position.j + 1 };
        isForward = forwardInternal(newPos, paths, oldPath) || isForward;
      }
    }

    return isForward;
  }

  int m_row = 0, m_column = 0, m_maxValue = 0;
  std::vector<std::vector<int>>* m_grid;
};

//TEST(test2684, test2684_1) {
//  std::vector<std::vector<int>> grid = {
//    {3,2,4} ,{2,1,9},{1,1,7}
//  };
//  Solution s;
//  std::cerr << "maxMoves: " << s.maxMoves(grid) << std::endl;
//}

TEST(test2684, test2684_2) {
  std::vector<std::vector<int>> grid = {
    {1000000, 92910, 1021, 1022, 1023, 1024, 1025, 1026,
     1027, 1028, 1029, 1030, 1031, 1032, 1033, 1034, 1035,
     1036, 1037, 1038, 1039, 1040, 1041, 1042, 1043, 1044,
     1045, 1046, 1047, 1048, 1049, 1050, 1051, 1052, 1053,
     1054, 1055, 1056, 1057, 1058, 1059, 1060, 1061, 1062,
     1063, 1064, 1065, 1066, 1067, 1068},
    {1069, 1070, 1071, 1072, 1073, 1074, 1075, 1076, 1077,
     1078, 1079, 1080, 1081, 1082, 1083, 1084, 1085, 1086,
     1087, 1088, 1089, 1090, 1091, 1092, 1093, 1094, 1095,
     1096, 1097, 1098, 1099, 1100, 1101, 1102, 1103, 1104,
     1105, 1106, 1107, 1108, 1109, 1110, 1111, 1112, 1113,
     1114, 1115, 1116, 1117, 1118}
  };
  Solution s;
  LOGGER_DEBUG("maxMoves: %d", s.maxMoves(grid));
}

